package random;

import java.util.Arrays;

/**
 * 二维区域和检索 -矩阵不可变
 *
 * 给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
 *
 */

public class L304 {

    public static void main(String[] args) {

        int[][] matrix = {{3, 0, 1, 4, 2},
                          {5, 6, 3, 2, 1},
                          {1, 2, 0, 1, 5},
                          {4, 1, 0, 1, 7},
                          {1, 0, 3, 0, 5}};
        NumMatrix numMatrix = new NumMatrix(matrix);
        int result = numMatrix.sumRegion(1, 2, 2, 4);
        System.out.println(result);
    }

    static class NumMatrix {

        // 先把那一个所在的集合的和求出来，调用的时候直接就是根据这个和的二维数组进行运算就可以了
        int[][] sumMatrix;
        public NumMatrix(int[][] matrix) {

            if (matrix.length == 0) {
                sumMatrix = null;
            }else {
                int row = matrix.length;
                int col = matrix[0].length;
                sumMatrix = new int[row][col];
                for (int i = 0; i < row; i++) {
                    int sum = 0;
                    for (int j = 0; j < col; j++) {
                        sum += matrix[i][j];
                        sumMatrix[i][j] = sum;
                        if (i != 0) sumMatrix[i][j] += sumMatrix[i-1][j];
                    }
                }
            }

        }

        public int sumRegion(int row1, int col1, int row2, int col2) {

            // 可以使用三目运算简化
            int num = -1;
            if (col1 == 0 && row1 != 0){
                 num = sumMatrix[row2][col2] - sumMatrix[row1-1][col2];
            }else if (col1 != 0 && row1 == 0) {
                num = sumMatrix[row2][col2] - sumMatrix[row2][col1-1];
            }else if (col1 != 0 && row1 != 0){
                num = sumMatrix[row2][col2] - sumMatrix[row1-1][col2] - sumMatrix[row2][col1-1] + sumMatrix[row1-1][col1-1];
            }else {
                if (sumMatrix != null) {
                    num = sumMatrix[row2][col2];
                }
            }
            return  num;
        }
    }
}
